package com.lk.common.utils.datastructure;


public class QuickSort {
	public static void main(String[] args) {  
		String str = "gmidfjgfuidngd";
		char[] charArr = str.toCharArray();
		if(charArr.length>0) {
			quickSort(charArr,0,charArr.length-1);
		}
		System.out.println(charArr);
    }  
  
	public static void quickSort(char[] charArr,int low,int height) {
		
		//递归方法出口
		if(low>height) {
			return ;
		}
		
		//赋值
		int i = low;
		int j = height;
		char key = charArr[low];
		
		//循环进行一轮判断和交换值
		while(i<j) {
			
			while(i<j && charArr[j]>key) {
				j--;
			}
			
			while(i<j && charArr[i]<=key) {
				i++;
			}
			
			if(i<j) {
				char p = charArr[j];
				charArr[j] = charArr[i];
				charArr[i] = p;
			}
		}
		
		//完成最后一趟排序
		char p = charArr[i];
		charArr[i] = charArr[low];
		charArr[low] = p;
		
		//左边进行排序
		quickSort(charArr,low,i-1);
		
		//右边进行排序
		quickSort(charArr,i+1,height);
	}
	
   /* public static void quickSort(int[] a) {  
        if(a.length>0) {  
            quickSort(a, 0 , a.length-1);  
        }  
    }  
  
    private static void quickSort(int[] a, int low, int high) {  
        //1,找到递归算法的出口  
        if( low > high) {  
            return;  
        }  
        //2, 存  
        int i = low;  
        int j = high;  
        //3,key  
        int key = a[ low ];  
        //4，完成一趟排序  
        while( i< j) {  
            //4.1 ，从右往左找到第一个小于key的数  
            while(i<j && a[j] > key){  
                j--;  
            }  
            // 4.2 从左往右找到第一个大于key的数  
            while( i<j && a[i] <= key) {  
                i++;  
            }  
            //4.3 交换  
            if(i<j) {  
                int p = a[i];  
                a[i] = a[j];  
                a[j] = p;  
            }  
        }  
        // 4.4，调整key的位置  
        int p = a[i];  
        a[i] = a[low];  
        a[low] = p;  
        //5, 对key左边的数快排  
        quickSort(a, low, i-1 );  
        //6, 对key右边的数快排  
        quickSort(a, i+1, high);  
    }  */
}
